package com.topInterview;

import java.util.List;

public class leecode139 {
    public boolean wordBreak(String s, List<String> dics) {
        return process(s, 0, dics) != 0;
    }

    public int process(String s, int index, List<String> dics) {
        if (index == s.length()) {
            return 1;
        }

        int ways = 0;
        for (int end = index; end < s.length(); end++) {
            String pre = s.substring(index, end + 1);
            if (dics.contains(pre)) {
                ways += process(s, index + 1, dics);
            }
        }
        return ways;
    }

    public boolean wordBreak2(String s, List<String> dics) {
        int N = s.length();
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i++) {
            int ways = 0;
            for (int end = i; end < s.length(); end++) {
                String pre = s.substring(i, end + 1);
                if (dics.contains(pre)) {
                    ways += dp[i + 1];
                }
            }
            dp[i] = ways;

        }


        return dp[0] != 0;
    }

}
